package leetcode.code0132;

public class Solution2 extends Solution132 {

	@Override
	public int minCut(String s) {
		int len = s.length();
		char[] cc = s.toCharArray();
		int[][] dp = new int[len][len];
		dp[len - 1][len - 1] = 0;
		for (int i = len - 2; i >= 0; i--) {
			dp[i][i] = 0;
			char left = cc[i];
			for (int j = i + 1; j < len; j++) {
				char right = cc[j];
				if (i + 1 == j) {
					dp[i][j] = left == right ? 0 : 1;
				} else {
					if (dp[i + 1][j - 1] == 0 && left == right) {
						dp[i][j] = 0;
					} else {
						int min = Integer.MAX_VALUE;
						for (int k = i; k < j; k++) {
							min = Math.min(min, dp[i][k] + dp[k + 1][j] + 1);
						}
						dp[i][j] = min;
					}
				}
			}
		}
		return dp[0][len - 1];
	}

	public static void main(String[] args) {
		Solution2 so = new Solution2();
		so.debug1();
		so.debug2();
		so.debug3();
		so.debug4();
		so.debug5();

	}

}
